/*
 * Program to solve suduko puzzle
 */

#include <stdio.h>
#include <string.h>
#include <time.h>

#define MAX	9

struct _nextS {
    int res;
    int r;
    int c;
} nextS[MAX][MAX];

int ps[MAX*MAX][MAX + 1];

int s[MAX][MAX], o[MAX][MAX];
int n, N, nosolution,
first_r, first_c; /*first non-zero (row,col) with the least number of possible candidates */

void print(void) {
    int i, j;

    for (i = 0; i < N; i++) {
        printf("%d", s[i][0]);
        for (j = 1; j < N; j++)
            printf(" %d", s[i][j]);
        printf("\n");
    }
}

int canbefilled(int r, int c, int nextD) {
    int ans, si, sj, i, j;

    if (n == 3) {
        if (r >= 0 && r <= 2) si = 0;
        else if (r >= 3 && r <= 5) si = 3;
        else if (r >= 6 && r <= 8) si = 6;

        if (c >= 0 && c <= 2) sj = 0;
        else if (c >= 3 && c <= 5) sj = 3;
        else if (c >= 6 && c <= 8) sj = 6;
    } else if (n == 2) {
        if (r >= 0 && r <= 1) si = 0;
        else if (r >= 2 && r <= 3) si = 2;

        if (c >= 0 && c <= 1) sj = 0;
        else if (c >= 2 && c <= 3) sj = 2;
    } else if (n == 1) {
        si = 0;
        sj = 0;
    }

    ans = nextD;

    for (i = 0; i < N; i++)
        if (s[r][i] == nextD)
            ans = 0;

    for (i = 0; i < N; i++)
        if (s[i][c] == nextD)
            ans = 0;

    for (i = si; i < si + n; i++)
        for (j = sj; j < sj + n; j++)
            if (s[i][j] == nextD)
                ans = 0;

    return ans;
}

int compute_possible_candidates(void) {
    int i, j, nextD, k, min = 10, d, ans = 0;

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            ps[i * N + j][0] = 0;
            if (o[i][j] == 0) {
                k = 0;
                for (nextD = 1; nextD <= 9; nextD++) {
                    if (canbefilled(i, j, nextD)) {
                        ps[i * N + j][nextD] = 1;
                        d = nextD;
                        k++;
                    }
                }

                ps[i * N + j][0] = k;
                if (k == 1) {
                    o[i][j] = d;
                    s[i][j] = d;
                    ans = 1;
                } else if (k < min) {
                    min = k;
                    first_r = i;
                    first_c = j;
                }
            }
        }
    }

    return ans;
}

/* return the next square which is not originally filled */
int getnext(int *nr, int*nc) {
    int r, c;

    if (*nc == N) {
        *nr = *nr + 1;
        *nc = 0;
    }

    if (*nr == N)
        *nr = 0;

    for (r = *nr; r < N; r++) {
        for (c = *nc; c < N; c++)
            if (o[r][c] == 0) {
                *nr = r;
                *nc = c;
                return 1;
            }
        *nc = 0;
    }

    for (r = 0; r < N; r++) {
        for (c = 0; c < N; c++)
            if (o[r][c] == 0) {
                *nr = r;
                *nc = c;
                return 1;
            }
        *nc = 0;
    }

    return 0;
}

int nf;

int fillpos(int r, int c) {
    int ans, nextD, nr, nc;
    nf++;
    do {
        for (nextD = (s[r][c] ? s[r][c] : 1); nextD <= N; nextD++)
            if (canbefilled(r, c, nextD)) {
                s[r][c] = nextD;
                break;
            }

        if (nextD > N) {
            if (r == first_r && c == first_c) {
                /* We tried everything, backtracking every path.
                   Now even first_r,first_c can't be filled */
                nosolution = 1;
                return 1;
            }

            s[r][c] = 0;
            return 0;
        }

        if (nextS[r][c].res == 0)
            return 1;
        else {
            nr = nextS[r][c].r;
            nc = nextS[r][c].c;
        }

        ans = fillpos(nr, nc);
    } while (!ans);

    return 1;
}

void suduko() {
    int i, j, a, b;

    time_t t1, t2;
    (void) time(&t1);
    freopen("suduko.in", "r", stdin);

    while (scanf("%d", &n) != EOF) {
        N = n*n;
        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++) {
                scanf("%d", &s[i][j]);
                o[i][j] = s[i][j];
                nextS[i][j].res = 0;
            }

        if (n == 1) {
            printf("1\n");
        } else {
            memset(ps, 0, sizeof (ps));
            first_r = first_c = 0;
            while (compute_possible_candidates());

            i = first_r;
            j = first_c;
            a = first_r;
            b = first_c + 1;
            while (getnext(&a, &b)) {
                if (a == first_r && b == first_c)
                    break;

                nextS[i][j].res = 1;
                nextS[i][j].r = a;
                nextS[i][j].c = b;
                i = a;
                j = b;
                b = b + 1;
            }

            a = first_r;
            b = first_c;
            nosolution = 0;
            if (getnext(&a, &b))
                fillpos(a, b);
            if (nosolution)
                printf("NO SOLUTION\n");
            else print();
        }
    }

    (void) time(&t2);
    printf("Time taken:%d\n", (int) (t2 - t1));

    return ;
}

/* suduko.in

3
7 0 8 0 0 0 3 0 0
0 0 0 2 0 1 0 0 0
5 0 0 0 0 0 0 0 0
0 4 0 0 0 0 0 2 6
3 0 0 0 8 0 0 0 0
0 0 0 1 0 0 0 9 0
0 9 0 6 0 0 0 0 4
0 0 0 0 7 0 5 0 0
0 0 0 0 0 0 0 0 0

 */